Search results for "Abstract state machines"
showing 5 items of 5 documents
Eventual Consistency Formalized
2019
Distribution of computation is well-known, and there are several frameworks, including some formal frameworks, that capture distributed computation. As yet, however, models of distributed computation are based on the idea that data is conceptually centralized. That is, they assume that data, even if it is distributed, is consistent. This assumption is not valid for many of the database systems in use today, where consistency is compromised to ensure availability and partition tolerance. Starting with an informal definition of eventual consistency, this paper explores several measures of inconsistency that quantify how far from consistency a system is. These measures capture key aspects of e…
Concurrent Computing with Shared Replicated Memory
2019
Any concurrent system can be captured by a concurrent Abstract State Machine (cASM). This remains valid, if different agents can only interact via messages. It even permits a strict separation between memory managing agents and other agents that can only access the shared memory by sending query and update requests. This paper is dedicated to an investigation of replicated data that is maintained by a memory management subsystem, where the replication neither appears in the requests nor in the corresponding answers. We specify the behaviour of a concurrent system with such memory management using concurrent communicating ASMs (ccASMs), provide several refinements addressing different replic…
What is the Natural Abstraction Level of an Algorithm?
2021
Abstract State Machines work with algorithms on the natural abstraction level. In this paper, we discuss the notion of the natural abstraction level of an algorithm and how ASM manage to capture this abstraction level. We will look into three areas of algorithms: the algorithm execution, the algorithm description, and the algorithm semantics. We conclude that ASM capture the natural abstraction level of the algorithm execution, but not necessarily of the algorithm description. ASM do also capture the natural abstraction level of execution semantics.
Distributed Computing on Distributed Memory
2018
Distributed computation is formalized in several description languages for computation, as e.g. Unified Modeling Language (UML), Specification and Description Language (SDL), and Concurrent Abstract State Machines (CASM). All these languages focus on the distribution of computation, which is somewhat the same as concurrent computation. In addition, there is also the aspect of distribution of state, which is often neglected. Distribution of state is most commonly represented by communication between active agents. This paper argues that it is desirable to abstract from the communication and to consider abstract distributed state. This includes semantic handling of conflict resolution, e.g. i…
Distributed ASM - Pitfalls and solutions
2014
Published version of a chapter in the book: Abstract State Machines, Alloy, B, TLA, VDM, and Z. Also available from the publisher at: http://dx.doi.org/10.1007/978-3-662-43652-3_18 While sequential Abstract State Machines (ASM) capture the essence of sequential computation, it is not clear that this is true of distributed ASM. This paper looks at two kinds of distributed process, one based on a global state and one based on variable access. Their commonalities are extracted and conclusions for the general understanding of distributed computation are drawn, providing integration between global state and variable access.